#include <iostream>
#include <string>
#include <vector>       //vector<bool>
#include <iterator>
#include <algorithm>
#include <limits>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>      //strlen()
#include <climits>      //ULONG_MAX
#include <cmath>      //ULONG_MAX
using namespace std;
class BigInt {
	private:
		unsigned char *digits;
		unsigned long int length;
		unsigned long int digitCount;
		bool positive;
		static const double FACTOR;
		static unsigned long int int2uchar(     unsigned long int number, 
				unsigned char *digits, 
				unsigned long int padding);
		static int compareNumbers(      unsigned char *a, unsigned long int na,
				unsigned char *b, unsigned long int nb, 
				bool aPositive = true, 
				bool bPositive = true);
		static unsigned long int toInt(unsigned char *digits, int n);
		void char2uchar(unsigned char *array, unsigned long int length);
		bool allCharsAreDigits( const char *array, unsigned long int length);
		static bool add(unsigned char *shorter, unsigned long int nShorter, 
				unsigned char *longer, unsigned long int nLonger, 
				unsigned char *result, int nResult, 
				bool doFill = true);
	public:
		BigInt();
		BigInt(const char *charNum);
		BigInt(unsigned long int intNum);
		BigInt(const std::string &str);
		BigInt(const BigInt &number);
		BigInt &operator =(const BigInt &rightNumber);
		BigInt &operator =(unsigned long int intNum);
		~BigInt();
		operator std::string() const;
		friend std::ostream &operator <<(       std::ostream &cout, 
				const BigInt &number);
		friend std::istream &operator >>(       std::istream &cin, 
				BigInt &number);
		friend BigInt operator + (const BigInt &a, const BigInt &b);
		BigInt &operator+();
		BigInt &operator+=(const BigInt &number);
		unsigned long int Length() const;
		std::string ToString(bool forceSign = false) const;
};

inline BigInt::~BigInt()
{
	delete[] digits;
}

inline BigInt &BigInt::operator+()
{
	return *this;
}

inline unsigned long int BigInt::Length() const
{
	return digitCount;
}

static const BigInt BigIntZero;
static const BigInt BigIntOne(1L);
const double BigInt::FACTOR = 1.6;
static const BigInt ULongMax(ULONG_MAX);
static const BigInt SqrtULongMax
(static_cast<unsigned long int>(sqrt(static_cast<double>(ULONG_MAX))));

unsigned long int BigInt::int2uchar(unsigned long int number, 
		unsigned char *digits, 
		unsigned long int padding = 0L)
{
	int i(0);
	do
	{
		digits[i++] = (unsigned char) (number % 10);
		number /= 10;
	} while (number > 0L);

	std::fill_n(digits + i, padding, 0);
	return i;
}

int BigInt::compareNumbers(     unsigned char *a, unsigned long int na,      
		unsigned char *b, unsigned long int nb,
		bool aPositive, bool bPositive)
{
	if (na < nb || !aPositive && bPositive)
		return 2;
	else if (na > nb || aPositive && !bPositive)
		return 1;

	for (long int i = na - 1; i >= 0L; i--)
		if (a[i] != b[i])
		{
			if (a[i] < b[i])    // |a| < |b|
				if (aPositive)
					return 2;       // a < b
				else
					return 1;       // a > b
			else                                // |a| > |b|
				if (aPositive)  
					return 1;       // a > b
				else
					return 2;       // a < b
		}
	return 0;
}


bool BigInt::add(unsigned char *shorter, unsigned long int nShorter,
		unsigned char *longer, unsigned long int nLonger, 
		unsigned char *result, int nResult, bool doFill)
{
	unsigned char subSum(0);
	unsigned char subCarry(0);

	unsigned long int i(0L);

	for (; i < nShorter; i++)
	{
		subSum = longer[i] + shorter[i] + subCarry;
		subCarry = subSum / 10;
		result[i] = subSum % 10;
	}

	for (; i < nLonger; i++)
	{
		subSum = longer[i] + subCarry;
		subCarry = subSum / 10;
		result[i] = subSum % 10;
	}

	if (doFill)
		std::fill_n(result + i, nResult - i, 0);

	if (subCarry)
	{
		result[i++] = 1;
		return true;
	}
	return false;
}

BigInt::BigInt() : digits(0), length(10), digitCount(1), positive(true)
{
	try
	{
		digits = new unsigned char[length];
	}
	catch (...)
	{
		delete[] digits;
		throw "Error BIGINT02: BigInt creation error (out of memory?).";
	}

	digits[0] = 0;
}

void BigInt::char2uchar(unsigned char *array, unsigned long int length)
{
	for (unsigned long int i(0L); i < length; i++)
		array[i] -= '0';
}

bool BigInt::allCharsAreDigits( const char *array, unsigned long int length)
{
	for (unsigned long int i(0L); i < length; i++)
		if (array[i] < '0' || array[i] > '9')
			return false;

	return true;
}

BigInt::BigInt(const char * charNum) : digits(0)
{
	digitCount = (unsigned long int) strlen(charNum);

	if (digitCount == 0L)
		throw "Error BIGINT03: Input string empty.";
	else 
	{
		switch (charNum[0])
		{
			case '+':
				digitCount--;
				charNum++;
				positive = true;
				break;
			case '-':
				digitCount--;
				charNum++;
				positive = false;
				break;
			default:
				positive = true;
		}
	}

	while (charNum[0] == '0')
	{
		charNum++;
		digitCount --;
	}

	if (! BigInt::allCharsAreDigits(charNum, digitCount))
		throw "Error BIGINT04: Input string contains characters"
			" other than digits.";

	if (charNum[0] == '\0')
	{
		digitCount = 1;
		charNum--;
		positive = true;
	}

	length = (unsigned long int)(digitCount * BigInt::FACTOR + 1);

	try
	{
		digits = new unsigned char[length];
	}
	catch (...)
	{
		delete[] digits;
		throw "Error BIGINT05: BigInt creation error (out of memory?).";
	}

	std::reverse_copy(charNum, charNum + digitCount, digits);
	BigInt::char2uchar(digits, digitCount);
}

BigInt::BigInt(unsigned long int intNum) : digits(0)
{
	positive = true;
	unsigned char tempDigits[40] = {0};
	digitCount = int2uchar(intNum, tempDigits);
	length = (unsigned long int)(digitCount * BigInt::FACTOR + 1);
	try
	{
		digits = new unsigned char[length];
	}
	catch (...)
	{
		delete [] digits;
		throw "Error BIGINT06: BigInt creation error (out of memory?).";
	}

	std::copy(tempDigits, tempDigits + digitCount, digits);
}

BigInt::BigInt(const std::string &str) :        digits(0), length(10), 
	digitCount(1), positive(true)
{
	try
	{
		digits = new unsigned char[length];
	}
	catch (...)
	{
		delete[] digits;
		throw "Error BIGINT07: BigInt creation error (out of memory?).";
	}

	//initialize to 0
	digits[0] = 0;
	BigInt a(str.c_str());
	*this = a;
}

BigInt::BigInt(const BigInt &rightNumber) : length(rightNumber.length),
	digitCount(rightNumber.digitCount), positive(rightNumber.positive)
{
	if (length <= digitCount + 2 || length > (digitCount << 2))
		length = (unsigned long int) (digitCount * BigInt::FACTOR + 1);
	try
	{
		digits = new unsigned char[length];
	}
	catch (...)
	{
		delete[] digits;
		throw "Error BIGINT08: BigInt creation error (out of memory?).";
	}

	std::copy(rightNumber.digits, rightNumber.digits + digitCount, digits);
}

BigInt::operator std::string() const
{
	return ToString();
}

BigInt &BigInt::operator =(const BigInt &rightNumber)
{
	if (length < rightNumber.digitCount + 2 || 
			length > (rightNumber.digitCount << 2)) 
	{
		length = (unsigned long int) 
			(rightNumber.digitCount * BigInt::FACTOR + 1);
		unsigned char *tempDigits(digits);

		try
		{
			digits = new unsigned char[length];
		}
		catch (...)
		{
			delete[] digits;
			digits = tempDigits;
			throw "Error BIGINT09: BigInt assignment error (out of memory?).";
		}
		delete[] tempDigits;
	}
	else if (this == &rightNumber)
		return *this;

	digitCount = rightNumber.digitCount;
	positive = rightNumber.positive;
	std::copy(rightNumber.digits, rightNumber.digits + digitCount, digits);
	return *this;
}

BigInt &BigInt::operator =(unsigned long int intNum) {
	positive = true;
	unsigned char tempDigits[40] = {0};
	unsigned long int rdigitCount = int2uchar(intNum, tempDigits);
	unsigned long int rlength = (unsigned long int)(digitCount * BigInt::FACTOR + 1);
	if (length < rdigitCount + 2 || length > (rdigitCount << 2)) 
	{
		length = rlength;
		unsigned char *temp(digits);
		try
		{
			digits = new unsigned char[length];
		}
		catch (...)
		{
			delete [] digits;
			digits = temp;
			throw "Error BIGINT06: BigInt creation error (out of memory?).";
		}
		delete[] temp;
	}
	digitCount = rdigitCount;
	std::copy(tempDigits, tempDigits + digitCount, digits);
	return *this;
}

std::ostream &operator <<(std::ostream &cout, const BigInt &number)
{
	if (!number.positive)
		cout << '-';
	for (int i = number.digitCount - 1; i >= 0; i--)
		cout << (int(number.digits[i]));

	return cout;
}

BigInt operator +(const BigInt &a, const BigInt &b)
{
	const BigInt *shorter, *longer;
	if (BigInt::compareNumbers(     a.digits, a.digitCount, 
				b.digits, b.digitCount) == 1)
	{
		shorter = &b;
		longer = &a;
	}
	else
	{
		shorter = &a;
		longer = &b;
	}

	BigInt sum(*longer);

	bool overflow = BigInt::add(shorter->digits, shorter->digitCount, 
			longer->digits, longer->digitCount, 
			sum.digits, 0, false);
	if (overflow)
		sum.digitCount++;

	return sum;
}

BigInt &BigInt::operator+=(const BigInt &number)
{
	*this = *this + number;
	return *this;
}


std::string BigInt::ToString(bool forceSign) const
{
	std::string number;
	if (!positive)
		number.push_back('-');
	for (int i = digitCount - 1; i >= 0; i--)
		number.push_back(char(digits[i]) + '0');

	return number;
}

const unsigned short sz = 350;
const string array[sz] = {\
"0",\
"2",\
"5",\
"13",\
"33",\
"84",\
"214",\
"545",\
"1388",\
"3535",\
"9003",\
"22929",\
"58396",\
"148724",\
"378773",\
"964666",\
"2456829",\
"6257097",\
"15935689",\
"40585304",\
"103363394",\
"263247781",\
"670444260",\
"1707499695",\
"4348691431",\
"11075326817",\
"28206844760",\
"71837707768",\
"182957587113",\
"465959726754",\
"1186714748389",\
"3022346810645",\
"7697368096433",\
"19603797751900",\
"49927310410878",\
"127155786670089",\
"323842681502956",\
"824768460086879",\
"2100535388346803",\
"5349681918283441",\
"13624667685000564",\
"34699552676631372",\
"88373454956546749",\
"225071130274725434",\
"573215268182628989",\
"1459875121596530161",\
"3718036641650414745",\
"9469163673079988640",\
"24116239109406922186",\
"61419678533544247757",\
"156424759849575406340",\
"398385437342101982623",\
"1014615313067323619343",\
"2584040823326324627649",\
"6581082397062074857264",\
"16760820930517797961520",\
"42686765081423995407953",\
"108715433490427863634690",\
"276878452992797520638853",\
"705159104557446900320349",\
"1795912095598119184914241",\
"4573861748746482790787684",\
"11648794697648531666809958",\
"29667363239641665309321841",\
"75557382925678345076241324",\
"192430923788646887128614447",\
"490086593742613784642792059",\
"1248161494199552801490439889",\
"3178840505930366274752286284",\
"8095929099802899135637804516",\
"20618860199735717347518335205",\
"52512490005204700105426761210",\
"133739769309948016694009662141",\
"340610888824836450840964420697",\
"867474036964825618481365264745",\
"2209298732064435704497704612328",\
"5626682389918533478317738910098",\
"14330137548866328279614547697269",\
"36496256219715625742044538916964",\
"92949332378216113242021364441295",\
"236725058525014180505701815496823",\
"602895705647960099995469534351905",\
"1535465802199150493738662248641928",\
"3910552368571275267978495847132584",\
"9959466244989661129691123477259001",\
"25364950660749748021099405050292514",\
"64599919935060432439868429424976613",\
"164524256775860274030527387377504741",\
"419013384147530728522022609230278609",\
"1067150945005982163514441035263038572",\
"2717839530935355329581432067133860494",\
"6921843391024223551199327778761038169",\
"17628677257989784595494528659918975404",\
"44897037437939148071769817165732849471",\
"114344595524892304290233490770145712515",\
"291214905745713541247731327365943249905",\
"741671444454258534857465962667765061796",\
"1888902390179122915252896743471619086012",\
"4810691130558217906610990776976946483725",\
"12251956095749817263332344260093277115258",\
"31203505712236975348528576040635119800253",\
"79469658650781985867000487118340463199489",\
"202394779109550764345861894537409323314489",\
"515462722582120489907252852233794229628720",\
"1312789882924573730027368086123338245771418",\
"3343437267540818714307850919017880044486045",\
"8515127140588331648550322776392892564372228",\
"21686481431642055741435864557927003419001919",\
"55231527271413261845729902811264779446862111",\
"140664663115056911081445992956849454877098369",\
"358247334933169139750057753282890692620060768",\
"912390860252808452427291402333895619564082016",\
"2323693718553842955686086550907531386625323169",\
"5918025632293663503549522257431849085434789122",\
"15072135843393978415212422468105125177058983429",\
"38385991037635463289660453744549630826178079149",\
"97762143550958568498082852214636235914849930849",\
"248982413982946578701038580641927227832936924276",\
"634112962554487189189820467243040322406901858550",\
"1614970482642879525578762367342644108561590572225",\
"4113036341823192819048383782570255767363019927276",\
"10475156128843752352865350399726195965694532285327",\
"26678319082153577050357846949365291807313675070155",\
"67944830634974099272629428081027035347684902352913",\
"173043136480945527948482053511145558468378012061308",\
"440709422679018732219951382052683444091754601545684",\
"1122406812473957091661014245697539481999572117505589",\
"2858566184107878443490461926958907966559276848618170",\
"7280248603368732710861889481668038859209880416287613",\
"18541470203319300956875255135992525166978609798698985",\
"47221755194115213068102861680611997159726376862303753",\
"120265229194918459803942867978884558345641243939594104",\
"306293683787271433632863852774373639017987474540190946",\
"780074351963576540137773435208243833541342569882279749",\
"1986707616909342973712353591169745864446313858244344548",\
"5059783269569533921195344470322109201451957760911159791",\
"12886348508011987356240815967022208100891571949948943879",\
"32819187902502851607389329995536271267681415519053392097",\
"83584507582587224492214820428416859837706360748966887864",\
"212874551575689287948059786819392199043985708966936111704",\
"542152798636468651995723724062737529193359194201892503369",\
"1380764656431213816431722055373284117268410458119688006306",\
"3516556663074585572807227621628697962774165819408204627685",\
"8956030781216853614041901022693417572010101291137989765045",\
"22809382881939506617322751722388817224062778859803872164081",\
"58091353208170452421494632089099749982909824830153938720892",\
"147948120079497265074353916923281734761892529811249739370910",\
"376796976249104489187525217658052036730757663312457289626793",\
"959633425785876695870898984328485558206317681266318257345388",\
"2444011947900355146003677103238304887905285555656343543688479",\
"6224454297835691477065778408463147370747646455891462634349139",\
"15852553969357614796006132904493085187606896148705587069732145",\
"40373574184451276215081721320687622633866724308958980317501908",\
"102824156636095858703235353954331477826087991222515010339085100",\
"261874441426000608417558562133843663473649602902694588065404253",\
"666946613672548351753434199542706427407253921336863166787395514",\
"1698591825407193170627662315173587996114245436798935931979280381",\
"4326004705912935301426317392023726083109394397837429618811360529",\
"11017547850905612125233731298763746589740288153810658336389396953",\
"28059692233131352722521442304724807258704216142257682223569434816",\
"71462937023081252871702933300237087190258114836163452402339627114",\
"182003114130199470591161040203962728228960733968395245364638085997",\
"463528857516611546776546456012887350906883798915211625355185233924",\
"1180523766186503817015956885529974517232986446634981948477348180959",\
"3006579504019818651399621267276799113601817426153570767674519681839",\
"7657211631742752666591745876096460095343505097857335109181572778561",\
"19501526533691827801599069904999693821521814068503222934515013419920",\
"49666844203146226921189506953372646851988950661017351745886119300240",\
"126492426571727034310569829687841447620843220488395261535468824798961",\
"322153223880292123343928236234055235915197205706311097751338782318082",\
"820465718535457507919615809109324566303226582562034808784032508735365",\
"2089577087522934173493729684140545816142493591318775976854872624587773",\
"5321773117461617978251003413624471434503410970905897860245116540228993",\
"13553589040981627637915352320498813251452542115692606506129138213781124",\
"34518528286947807427575437738762643753550988793609886849358265592379014",\
"87912418732338860471317231211648572193057930673818278065090785938768145",\
"223896954792607156008125252482558601391119392256939049485668975683696428",\
"570224856604500979915143173915528418728847703981306263885787002898540015",\
"1452259086733947976309728831525264011041872730893369855322333767419544603",\
"3698639984865004088542726089448615042203712558024985024016123513421325649",\
"9419763913068457133310324184338022514178145550924646167240367797160735916",\
"23990426897735866331473103289649924081601876390767647213819192875162342084",\
"61099257693405193884799256853086485719585610890484925618894877060906745733",\
"155608706197614711234381941180160918034951243722662144618849314794136569466",\
"396307096986370482685036242503058245871089974726576862070412699524342226749",\
"1009322157863760870489253683039363895496716804066300794378569590903727768697",\
"2570560118911506934897925549761946954899474826581840595446401196125934333609",\
"6546749492673145222970141025066316051166756431956558847341784682679938662664",\
"16673381262121558251327461282933942952729704494561259084508540152389539427634",\
"42464072135827768660522989140696148911525640247660917611805266183584951851541",\
"108148275026450240795343580589392556826947741421839653155460857202239381793380",\
"275434003450849808502537611602415205518150827585901483007235520740453254865935",\
"701480354063977626460941792934919116774775036841303536781737164866730843376791",\
"1786542986605255302219764778061645995894648642690348209726170707676154323412897",\
"4550000330725338039403008960660626314082223149807901439241314100959492745068520",\
"11588024002119909007486724492317817740833869979147454624990536074461870656926728",\
"29512591321570411356596222723357907791644611750793158898948556957559388382334873",\
"75163206975986069760082178899694259638205316630541673862128964090540140166664994",\
"191427029275662459884247305015064244808889114991023961248197021213101539372591589",\
"487529856848881400885173011653180657047628158363382755257471563474302607294183045",\
"1241649949949411331414675507221119818542350748348331145625269112252246894127622673",\
"3162256786023366523598771331110484538941218770051069007756206809191897934922019980",\
"8053693378845025779497391181095269553472416446813851916395154294110345371265845678",\
"20511293493662829414008229200522143464428402412027103986171784509664835571581334009",\
"52238537152194051131112620913250041021270440040919128896494930122631914449350533676",\
"133042061176895957455730862208117495060441698940679213695556799049039009841548247039",\
"338833952999648795456582574530007174606582240334304660273780312730374769704028361763",\
"862948504328387599500008632181381885294876619650207663139612354632420463698955504241",\
"2197773022833319951912330701100888440256777178575399200248561821044254706943487617284",\
"5597328502994676298781252608913165940415013217135310723910516309451304647289959100572",\
"14255378533151060148974844551108602206381680232496228311209206794579284465222361322669",\
"36305858592130116548643272412231258793435150860703166546577491719654128284678169363194",\
"92464424220405969545042641984484285733666995171037872128274706543338845681868659149629",\
"235490085566093115787703400932308432467150821435275139114336111600911104113637848985121",\
"599750453944722317669092716261332409461403788902291316903524421464815182193822526483065",\
"1527455417675943720670931475439457537123625394410895645049659661073880314183151561100880",\
"3890151374862702874798659068072555916175805399159357746117179855213486914673763497669946",\
"9907508621346071787937342327845901778936639981631902454187543792965669325724501082923837",\
"25232624035230790171344275199203817011172710756834058299541927102218705880305917224618500",\
"64262908066670355005424551794326091717457866894459376799388577852616568001010099029830783",\
"163665948789917571970130721115701902225025084527384714352506626600417511208050616367203903",\
"416827429681736289117030269224933713178680746706062863803943758155670296297417248988857089",\
"1061583716220060505209615811359895420299844444833969818759782720764374671803895213374748864",\
"2703660810911774871506392613060426456003394720901387215676015826284837151113258292105558720",\
"6885732767725346537339431306705682045485314633342807113915758131489719270327829046574723393",\
"17536710062582528451394871037831685967273868432420971262267314810028650363572811598629754370",\
"44662813703802178311635565995429480436036446219086136854126403577831857148586710535939790853",\
"113748070237912231612005434335396328884832075503936052084435880097182083931074061717084059469",\
"289695664242209169987041305704053824172974465659379212285265478582224675374307645568737664161",\
"737802212426132749897723611738933457666817453041780613509093240839463291828276063390499178644",\
"1879048159332386901394493963517317068391441447246876491387887840358333342961933834066820080918",\
"4785594195333115722673752844477621418622674813194912808570134400138354653126451377092877004641",\
"12188038762424751096639723264211493363303608526678482722037249881474505941043112651643073268844",\
"31040719879515004817347693336417925213621333313798754744032522003445699878174610514445843623247",\
"79055072716787876454008862781524965209168949967470905018672428288504260350518785057627637519979",\
"201338904075515508822005142163679348995262841775419047503414628461928726520255293281344191932049",\
"512773600747333898915366840445301588413315966832107754769534207215807413269203982134761865007324",\
"1305941178286971183106747685835807491031063725407105462061155471182047813409182042608495559466676",\
"3325994861396791773950867354280595919470706259421737726395259778041831766607823360633097175872725",\
"8470704501827888629923849234842300918385792211082688669621209234481518759894032746009451776219450",\
"21573345043339540216905313509801005247273354406994220527698833718186917099805070895260496287778301",\
"54943389449903760837685343608724907332403207284492867451414136448897184726111997897163541527648777",\
"139930828444974950522199849962093120830465561187062644100148315850462805311923099435597031119295305",\
"356378391383193202098990357042712154240607684065612376179409601868009712449763267663618100054017688",\
"907631000661265115557865907656242336644084136602780263910381656035379414937561632659996772754979458",\
"2311571221150698383736922022317289948359241518458235548100321229789231347636809632419208676683271909",\
"5887151834345855085130700309333534387603174857584863736290433717481851822660944165162032226175540964",\
"14993505890503673669556188548640601060209675370230743284591570320788314407896259595403269901789333295",\
"38185734836503900807979999428932026456381767116504585853573895588847711986090272988387780706437479463",\
"97252127397857330370646887715838188360576384460824778728029795215965590202737749737340863540839833185",\
"247683495522722235218829963409249004237744211408384886594225056341567206799462032058472777689906479128",\
"630804853279805701616286813963268223292446574394099137770053803487947715787752086842674199627090270904",\
"1606545329480190968822050479051623639183213744657407940862362458533428228577703955481162040484926854121",\
"4091579007762909874479217735475764505896618275117299906089003776896371379742622029863471058286850458274",\
"10420508198285816419396772763966420874268896869286106890810423815814118703850700102050778356685718041573",\
"26539140733814733682094813742460229893617625758346921628572213867058037016021726189446189812143213395541",\
"67590368673678193658065617984362645167400766661097250054043855326826564115636774510806629039258995290929",\
"172140386279456937417622822475151941102688055949827528627470348336525283951145975313110226247346922018972",\
"438410281966406802175406076677126757266394504319099228937556765866935169033950451326473271346096052724414",\
"1116551318885948735426500593813768100802877831249123236556627735397222186134683652476863397978798022758729",\
"2843653306017761210446030086779814899974838222767173230678282584997904825254463731593310293551039020260844",\
"7242268212887877958493966844050524658018948781102568926850749671259967005677561566989957256426972116004831",\
"18444741050679465862860464368694632316815613616221434320936409662915061022744270518050088204383781275029235",\
"46975403620264570894660925668219604191625014236312610799401851582087993876420566334683443958745573686324145",\
"119637816504096485610676282549184365358084590869949224846590862498351015781262964754406933378301900763682356",\
"304695777679137007978873955135282967224609809592432494813519986241705086461690766361547398919733156488718092",\
"776004775482635072463085118487969903998929224291126825273032686563849182581065063812185175176513787427442685",\
"1976343145148503638515720474660407140580552849044635370206176221867754467405083858740324682651062632107285818",\
"5033386843458779357473400022944067152384644731972830060498905116541063203852923547654381939398372208130732413",\
"12819121607548697425925605639036511349348771537281422316477019141513730057691996017861273736624320835796193329",\
"32647973203704677847840331775677496991662740655580310063659119621436277786641999442117254095298076511830404889",\
"83148454858416832479079669213335572485058897580414872504294163500927348834828918449750163866618846067587735520",\
"211764004528087040231925275841385153311129307353691477388724465764804705513991832359478855565160089482802069258",\
"539324437118295590790770552671783376098980252943378137345402214651973037649454582610825129092237101545022278925",\
"1373561333623095054292546050398287477994148710820862624583823058569678129647729916030879277616253138640434362628",\
"3498211108892572739607787929309743485398406981938794863901772797556134002458906247032062539889903468308693073439",\
"8909307988526536124298892461689557824889942927641830489732770868333919172214996992705829486488297176802842788431",\
"22690388419568740042498118903087146613172441548043318467951137592793650476536630148474600790482750960554813012929",\
"57788295936556588948902918197173594536633233005667262289536818851477354127747163536687093607343702566221161887728",\
"147176288281208454064602847759123893511328850487019673536757546164082277904245954214554617491658453269799979576816",\
"374831260918542237120606732618508528172463375527749927831003048772435560412775702114270929381143360066375934054289",\
"954627106054849517254719231193314544392888834548186791488300462560430752857544521979783569861288875968773009573122",\
"2431261761309449725694648042764261510469569895111143184344361520057379344032110700288392686595379565273721932777349",\
"6191981889592291205764622049340346093504492000298223088008026551447625001334541624670839872433191366582592809182109",\
"15769852646548881654478611372638268241871442730255776151848715085513060099558738471609856001323051174407680560714689",\
"40162948943999504240416492837381144087716947355920918576049818242531124544484129268178944561674673280671675863388836",\
"102287732424140181341076219096740902510809829442395836391956378122022934189861538632638584997105589102333625096674470",\
"260508266438828748577047542403501217351208048970968367511811289572090053023765945005065970557208902659746606617452465",\
"663467214245797182735587796741124481300942874740253489991628775508734164781877557910949470673198067702498514194968236",\
"1689730427354563295389299354982491082463903627893871183887025218711581316777382599459603496900710627167077260104063407",\
"4303436335393752522091234049109607863579958179498964225277490502503986851360408701835222435031828224696399641020547515",\
"10960070312387865522307355249942831290924762861632053124433634999228289184280077561040997837637565144262375056340126673",\
"27913307387524046862095243903977761527893387530656941658031785719672146536697946423376821607207669140388227013804864268",\
"71090121422829711768589077107007962210291496102444900665774696941076569109036379109629863487084731649735228724970402724",\
"181053620545571335921580753367936517239401142597178796114014814601053573939050782203677546419014697584121059520085796389",\
"461110669901496430473845827746858758216987168827459434551836111862855863523835889940361777932321795958365574778946859770",\
"1174365081771393908637861485968661995883666976354542565883461735267841870095758941194030965770743021150587437802949918653",\
"2990894453989855583671149553052119267223722264133723362432774396999593177654404554532101255892822535843661509904932493465",\
"7617264659652601506454006419819759288548098673449448725300846641129884088928403940198595255488709888796276032391761765353",\
"19399788855066452505217023878660299840203586587387163378917929414527203225606971376123322732640985334586801012491405942824",\
"49407736823775362100559203730192478236178994112357498845569479867183883717796751246977341976663503093813539567279506144466",\
"125832527162269778212789437758865015601109673485551609795357735790024854750128877810276601941456701411010156179442179997109",\
"320472580003381371031355103126582809278601927670847881815202880861760796443661478243653868592217891250420652938655272081508",\
"816185423992807882376058847742223112394492522939604872271332977380730331355248585544561681102555987005665001624032230304591",\
"2078675955151266913996262236369894049668696647035609236153226571413246313904287527143053832738786566672760812366161912687799",\
"5294009914298723081399938423608594021010487744681671226392989001068983755607485118074323215172347011601607279295011327761697",\
"13482881207741520959172197931329305204084164659338556561210537550931944156474506348836261944186036576881640372580216798515784",\
"34338448284933031913740596522637098478847513710394393584967290674346118382460785342889900936283206732037648836821606837481064",\
"87453787691906307868053329400212096182789679824809014957538107900693164677003562152690387031924797052558545325518441801239609",\
"222728904876487168609019453254390596048511038019350980061254044026664391892942415997106936944318837414036379860438707238476066",\
"567250045729813676999832832431630386758659269573905368665013486628368066845349179489794161856845678612668953883217463115672805",\
"1444682784028020830476738447517863465748619256991970732348819125184093690260644337129385647689934991691932832952392075271061285",\
"3679344518662342506562329180721747914304408821577197813423905781023219839259580269745672394181034499410570999648440320896271441",\
"9370621867082519520601229641392989681116096169720271727861644173858901435625154056110524597908849669125743786132490180179276972",\
"23865271036855402378241526911025590742285220418009712001496013253925116400770532719096107237688668829353991404865812756525886670",\
"60780508459455666783646612644165919079990945827316893544277576462732354076425799764048411467467221827244297595512556014127321753",\
"154796909822849255466135981840750418583383208242363770817912810353248725989247286303303454770531962152968330382023414964959807148",\
"394239599142009580094160103236692346989042582730054147181599210423154922455690905089751428246219814962534949764425198700572822719",\
"1004056616566324082438102800958301031641459319529788958725388807662290924977054896246854722730438813905282527506386368380232774339",\
"2557149742097507000436501686994044828855344430031995835450289636100985498399047983886764328477629404926068335159221350425998178545",\
"6512595699903347663405266278183083036341190762323834776807567290287416844230841769110134807931917438719954147589254267932801954148",\
"16586397758470526409685137044318511933179185274209454347790813024338110111837786418353888667071903096271259157844116254671834861180",\
"42242540958941907483212042053814151731554905740774739307839482975064622566305462589704676470553353036188540798436708127702469855053",\
"107584075376257689039514487430129898432630187518082767740277346264754772088679553366873376416110526607368294902306786778009576525434",\
"273997089469927811971926153958392460529994466051149729136184988528912276855502355741805317969846309347196389760894397938393457767101",\
"697820795275055220466578837400728971224174025361156965320486806297643948365989727440188688826356498337949615222532290782498961914689",\
"1777222755396295941944598316189980301410972704291546427517435947388954945676161363989056072038669832630463915108265766281400958121913",\
"4526263395537574916327701623739082034576113899995399549491543689604466116573814811160106150873542472946073835199958221283694335925616",\
"11527570341746500995066580401068873341787374529643502491821010132895531127189780713749457062612111276860561200730714499631288591887834",\
"29358626834426872848405460742066809019561835663573950960650999902784483316629537602648076348136434859297660151769652986827672477823197",\
"74771087406137821608205203508941573415487159756786803962614553628068963877022670730205715909758523468401955339469978694570327883459844",\
"190428371988449017059882448161018829192323529706791061377701117291817942197864659776808965230265593072962132031440324875599616836630719",\
"484986458217462728576375560573046040819696054833942877678667788114489331589381527886471722718426144473623879554120281432597234034544479",\
"1235172375829512295820838772816052484247202799131463620697651247148865569253650386279958126576876405488611846479150866435364412789179521",\
"3145759581864936337277935554366169838506425182803661180451671399704038412294546960223196941102444548523809704543862339178925676449534240",\
"8011677997776847698953085442121438202079749219572728859279661834671431725432125834612823731500191647009855135120995826225812999722792480",\
"20404287953248144031004945211425098726913126421080582519708646316195767432412449015728802530679704248032131821265004858065916088684298721",\
"51966013486138072098240911419337805494412427244537555079148625866767005002551570826293625733962044691597928482194867881536570853540924162",\
"132347992923301135926439853492222147917817730129728421537285559884401209162947716502928877730103985278237843920775736447364870795488939525",\
"337066287285988487982125563615207200056961013925074980673428391951765190760859452847880183724849719496105748145011345634332228533203101933",\
"858446580981416183988931892141974353526152185224415937963290969654698595687218193024982870913765468962047268692993295597565898715436067553",\
"2186307442172121991886429201391378055027083114503635278137295891145563591298243555400774803282484642698438129451773673276828896759564176564",\
"5568127752611648655743915858539937663637279428156761474911311143897590969044564756674412661203584473855029275741551987785555920767767522614",\
"14181009528376835487363192810613227735827794156041574165923209148595444125074591261774582996603419059370543949627870944445506637010535289345",\
"36116454251537441622356730681157771190319950854743545084895025332234042810491990835624353457692907235294555304449067549953398091548402277868",\
"91982045784063367387820570031468707780104975293685425810624570956961120715103137689697702573192818003814683834267558032137858740875107367695",\
"234261555348041011885361063554708414486357695598155970872067376394751728365772857476794341600681962302294466922612054558674622210309152302603",\
"596621610731682832780899427822043307943140317344740912639654349078698620257140843478910739232249649843698172983940734699440501253041814250769",\
"1519486822595470044834980489230263738152743305581323221962000645509110089595157682124313522638374079993505496724761081989693483457267888171836",\
"3869856811270663934336221469837279198734984624105543327435723016491670527813229065204332126109679772133003633356074953237502090377886742897044"\
};

/* main
 *	f[n]:=2*f[n-1]+f[n-2]+f[n-3];
 *  * */
int main() {
	BigInt BigArr[652];
	BigArr[0] = BigInt(string("9855822055868480746288322856726865443565852871137150789473101027571149765478756656011888514089983274103210936420851723164138165466083188216693"));
	BigArr[1] = BigInt(string("25100987745603095471747847672521273824019433671961168128343925717143080148365900059352422676928020400332931002922539481555471904767321007502266")); 
	BigArr[2] = BigInt(string("63927654358345335624120239671606692290339704839165030373596675478348980590023785839921065994055703846902076575622005639512584065378611946118269")); 
	for(short i = 3; i <=651; i++) {
		BigArr[i] =  BigArr[i-1] + BigArr[i-1] + BigArr[i-2] + BigArr[i-3];
	}
	short n;
	cin >> n;
	do {
		if(n < 350) cout << array[n] << endl;
		else cout << BigArr[n-sz] << endl;	
		cin >> n;
	} while(cin.eof() == false);
	return 0;
}
